package com.zwj.interview.二叉树之使用两个队列;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 如何在一棵二叉树中找出它最低层最左边节点的值？假设二叉树中最少有一个节点。
 *
 */
public class 二叉树最底层最左边的值I {


    /**
     * 可以用一个变量bottomLeft来保存每一层最左边的节点的值。
     * 在遍历二叉树时，每当遇到新的一层时就将变量bottomLeft的值更新为该层第1个节点的值。
     * 当整棵二叉树都被遍历完之后，变量bottomLeft的值就是最后一次更新的值，也就是最后一层的第1个节点的值
     * https://leetcode-cn.com/problems/LwUNpT/
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(root);
        int bottomLeft = root.val;
        while (!queue1.isEmpty()) {
            TreeNode node = queue1.poll();
            //如果说node还有子节点，那么将子节点放到queue2中
            if (node.left != null) {
                queue2.offer(node.left);
            }
            if (node.right != null) {
                queue2.offer(node.right);
            }
            //queue1为空，说明一层已经遍历完了，将queue2赋值给queue1,queue2重新用一个新的
            if (queue1.isEmpty()) {
                queue1 = queue2;
                queue2 = new LinkedList<>();
                //此时的queue1如果不为空，说明就是到了下一层，那么这样循环取队列头部的节点就行
                if (!queue1.isEmpty()) {
                    bottomLeft = queue1.peek().val;
                }
            }
        }
        return bottomLeft;
    }





}
